package com.zjsru.oneDay202206;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/6/15
 * 找出第 K 小的数对距离
 * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
 *
 * 找出第 K 小的数对距离
 * 输入：nums = [1,3,1], k = 1
 * 输出：0
 * 解释：数对和对应的距离如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 距离第 1 小的数对是 (1,1) ，距离为 0 。
 *
 */
public class smallestDistancePair {
    //二分 + 双指针
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
         int l = 0, r = (int)1e6;
         while(l < r){
             int mid = l + r >> 1;
             if(check(nums,mid) >= k){
                 r = mid;
             }
             else{
                l = mid + 1;
             }
         }
         return r;
    }
    
    private int check(int[] nums, int x) {
        int n = nums.length, ans = 0;
        for (int i = 0,j = 1; i < n; i++) {
            while(j < n && nums[j] - nums[i] <= x) j++;
            ans += j - i - 1;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        smallestDistancePair smallestDistancePair = new smallestDistancePair();
        int[] nums = new int[]{1,3,1};
        int k = 1;
        System.out.println(smallestDistancePair.smallestDistancePair(nums, k));
    }
}
